1. Technical Field:
The present invention relates generally to arbitration in data processing systems. More specifically, the invention is directed to a method and apparatus that use a pseudo round-robin scheme and independent tokens to arbitrate access to shared system resources in a computer system.
2. Description of the Related Art:
Arbiters, in one form or another, are used in most advanced computer systems. An arbiter manages request from various parts of a data processing system for access to resources that are shared by several elements of the data processing system. For example, in a multi-processor system, several processors may want access to a memory device. If the memory device can handle only one request at a time, a device or method must exist to manage these competing requests. An arbiter's goal is to manage these competing request quickly and efficiently.
The selection of a particular arbiter for a given system is a critical design decision. Due to the arbiter's power in deciding which devices can access certain resources, overall system performance can be greatly enhanced or hindered by the selection of a certain arbiter.
One popular type or arbiter is a fixed-priority arbiter. This type of arbiter is simple to implement, but often, it does not ensure fairness when it comes to allowing access to a given computing device. For instance, a fixed-priority arbiter will often block low priority devices from having access to a shared resource when a high-priority device is constantly demanding access.
One solution to fixed-priority arbiters is a round-robin arbiter. This type arbiter ensures fairness by making sure that all devices eventually gain access to a shared resource. However, round robin arbiters often do not lend themselves to efficient implementation, as they are often slow and/or inefficient.